package com.axzh.interview.base;

public class ShortestPath {

	public static int MAX = Integer.MAX_VALUE / 4;

	// public static int nn = 10;
	// public static int[] dist = new int[nn];
	// public static int[] pre_path = new int[nn];

	public static void main(String[] args) {

		/*
		 * Edge[] edge = new Edge[10]; edge[0] = new Edge(0, 1, 6); edge[1] =
		 * new Edge(0, 2, 7); edge[2] = new Edge(1, 2, 8); edge[3] = new Edge(1,
		 * 3, 5); edge[4] = new Edge(1, 4, -4); edge[5] = new Edge(2, 3, -3);
		 * edge[6] = new Edge(2, 4, 9); edge[7] = new Edge(3, 1, -2); edge[8] =
		 * new Edge(4, 0, 2); edge[9] = new Edge(4, 3, 7); String[] names = {
		 * "s", "t", "y", "x", "z" }; int num = names.length; Vertex[] vertics =
		 * new Vertex[num]; int[] dist = new int[num]; int[] pre_path = new
		 * int[num]; for (int i = 0; i < num; i++) { vertics[i] = new
		 * Vertex(names[i]); } if (ShortestPath.fellmanFord(edge, num, 0, dist,
		 * pre_path)) { for (int i = 1; i < num; i++) { System.out.print("节点 " +
		 * i + ", 值: " + dist[i] + ", 路径: " + i); ShortestPath.print_path(i,
		 * pre_path); System.out.println(); } }
		 */

		int[][] dijkstra_graph = { { 0, 10, MAX, 5, MAX }, { MAX, 0, 1, 2, MAX }, { MAX, MAX, 0, MAX, 4 },
				{ MAX, 3, 9, 0, 2 }, { 7, MAX, 6, MAX, 0 } };
		// ShortestPath.dijkstra(dijkstra_graph, 1);

		ShortestPath.floydWarshall(dijkstra_graph);
	}

	public static boolean fellmanFord(Edge[] edge, int n, int s, int[] dist, int[] pre_path) {
		// int n = graph.length;
		for (int i = 0; i < n; i++) {
			dist[i] = MAX;
			pre_path[i] = -1;
			if (i == s) {
				dist[i] = 0;
				pre_path[i] = s;
			}
		}
		for (int i = 0; i < n - 1; i++) {
			for (int j = 0; j < edge.length; j++) {
				if (dist[edge[j].v] > dist[edge[j].u] + edge[j].w) {
					dist[edge[j].v] = dist[edge[j].u] + edge[j].w;
					pre_path[edge[j].v] = edge[j].u;
				}
			}
		}
		boolean flag = true;
		for (int i = 0; i < edge.length; i++) {
			if (dist[edge[i].v] > dist[edge[i].u] + edge[i].w) {
				flag = false;
				break;
			}
		}
		return flag;
	}

	public static void print_path(int s, int[] pre_path) {
		while (s != pre_path[s]) {
			if (s == pre_path[s]) {
				System.out.print(s);
				break;
			}
			s = pre_path[s];
			System.out.print("->" + s);
		}
	}

	public static void dijkstra(int[][] matrix, int s) {
		int n = matrix.length;
		int[] dist = new int[n];
		int[] pre_path = new int[n];
		int[] vertics = new int[n]; // store the vertex has been found
		for (int i = 0; i < n; i++) {
			dist[i] = matrix[s][i];
			pre_path[i] = (i == s ? s : (dist[i] == MAX ? -1 : s));
			vertics[i] = 0;
		}
		vertics[s] = 1;
		for (int i = 1; i < n; i++) {
			int min = MAX;
			int u = 0;
			for (int j = 0; j < n; j++) {
				if (vertics[j] != 1 && dist[j] < min) {
					min = dist[j];
					u = j;
				}
			}
			vertics[u] = 1;
			for (int j = 0; j < n; j++) {
				if (vertics[j] != 1 && dist[j] > dist[u] + matrix[u][j]) {
					dist[j] = dist[u] + matrix[u][j];
					pre_path[j] = u;
				}
			}
		}
		for (int i = 0; i < n; i++) {
			System.out.print(s + "节点到" + i + "节点，最短长度为：" + dist[i] + "，路径为: " + i);
			int j = i;
			while (j != pre_path[j]) {
				j = pre_path[j];
				System.out.print("->" + j);
			}
			System.out.println();
		}
	}

	public static void spfa() {

	}

	public static void floydWarshall(int[][] graph) {
		int n = graph.length;
		int[][] result = new int[n][n];
		// int[][][] dist = new int[n + 1][n + 1][n + 1];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i == j) {
					result[i][j] = 0;
					// dist[i][j][0] = 0;
				}
				result[i][j] = graph[i][j];
				// dist[i][j][0] = graph[i][j];
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < n; k++) {
					if (result[i][j] > result[i][k] + result[k][j]) {
						result[i][j] = result[i][k] + result[k][j];
					}
				}
			}
		}

		/*
		 * for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { for(int k=0;k<n;k++) {
		 * if(result[i][j]>result[i][k]+result[k][j]) {
		 * result[i][j]=result[i][k]+result[k][j]; } } } }
		 */
		/*
		 * for (int k = 1; k <= n; k++) { for (int i = 0; i <= n; i++) { for
		 * (int j = 0; j <= n; j++) { dist[i][j][k] = dist[i][j][k - 1]; if
		 * (dist[i][k][k - 1] + dist[k][j][k - 1] < dist[i][j][k]) {
		 * dist[i][j][k] = dist[i][k][k - 1] + dist[k][j][k - 1]; } } } }
		 */
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				System.out.print(result[i][j] + " ");
			}
			System.out.println();
		}
		/*
		 * for(int k=0;k<=n;k++) { for (int i = 0; i <= n; i++) { for (int j =
		 * 0; j <= n; j++) { if(dist[i][j][k]!=MAX) {
		 * System.out.print(dist[i][j][k] + " "); } } //System.out.println(); }
		 * System.out.println(); }
		 */
	}

	public static void ax_search() {

	}

	@SuppressWarnings("unused")
	private static class Vertex {
		String name;

		public Vertex(String name) {
			this.name = name;
		}
	}

	@SuppressWarnings("unused")
	private static class Edge {
		int u, v;
		int w;

		public Edge(int u, int v, int w) {
			super();
			this.u = u;
			this.v = v;
			this.w = w;
		}

	}
}
